首页 > 其他分享 >树状数组--区间信息维护

树状数组--区间信息维护

时间：2024-11-06 13:19:18浏览次数：3  
标签：return 树状 -- modify cin int 数组 ans query

树状数组

树状数组的学习可以看b站董晓算法的讲解（极力推荐）。

董老师树状数组博客

oiwiki

大概的思路

在这里插入图片描述在这里插入图片描述

在这里插入图片描述

无论是往点修往后跳还是求前缀和往前跳都是一次跳2k，k为x二进制最低有效位。

在这里插入图片描述

代码模版

template<typename T>
struct Fenwick{
    int n;
    vector<T> tr;
 
    Fenwick(int n) : n(n), tr(n + 1, 0){}
 
    int lowbit(int x){// 找到x最低有效位
        return x & -x;
    }
 
    void modify(int x, T c){// 点修
        for(int i = x; i <= n; i += lowbit(i)) tr[i] += c;
    }
 
    void modify(int l, int r, T c){// 区修
        modify(l, c);
        if (r + 1 <= n) modify(r + 1, -c);
    }
 
    T query(int x){// 前缀和
        T res = T();
        for(int i = x; i; i -= lowbit(i)) res += tr[i];
        return res;
    }
 
    T query(int l, int r){// 区间查询
        return query(r) - query(l - 1);
    }
 
    int find_first(T sum){// 查找第一个满足条件的下标（前缀和
        int ans = 0; T val = 0;
        for(int i = __lg(n); i >= 0; i--){
            if ((ans | (1 << i)) <= n && val + tr[ans | (1 << i)] < sum){
                ans |= 1 << i;
                val += tr[ans];
            }
        }
        return ans + 1;
    }
 
    int find_last(T sum){// 查找最后一个满足条件的下标（前缀和）
        int ans = 0; T val = 0;
        for(int i = __lg(n); i >= 0; i--){
            if ((ans | (1 << i)) <= n && val + tr[ans | (1 << i)] <= sum){
                ans |= 1 << i;
                val += tr[ans];
            }
        }
        return ans;
    }
 
};
using BIT = Fenwick<int>;

点修+区查

P3374 【模板】树状数组 1

https://www.luogu.com.cn/problem/P3374

点修+区查是操作最简单的，直接用要维持的数据来建树，然后单点修改的话就直接对这个点进行modify，区间查询的话就对这个区间query(l,r)；

#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
//#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
template<typename T>
struct Fenwick{
    int n;
    vector<T> tr;
 
    Fenwick(int n) : n(n), tr(n + 1, 0){}
 
    int lowbit(int x){// 找一个数的最低有效位
        return x & -x;
    }
 
    void modify(int x, T c){// 点修
        for(int i = x; i <= n; i += lowbit(i)) tr[i] += c;
    }
 
    void modify(int l, int r, T c){// 区修
        modify(l, c);
        if (r + 1 <= n) modify(r + 1, -c);
    }
 
    T query(int x){// 查询前缀和
        T res = T();
        for(int i = x; i; i -= lowbit(i)) res += tr[i];
        return res;
    }
 
    T query(int l, int r){// 查询区间和
        return query(r) - query(l - 1);
    }
 
    int find_first(T sum){
        int ans = 0; T val = 0;
        for(int i = __lg(n); i >= 0; i--){
            if ((ans | (1 << i)) <= n && val + tr[ans | (1 << i)] < sum){
                ans |= 1 << i;
                val += tr[ans];
            }
        }
        return ans + 1;
    }
 
    int find_last(T sum){
        int ans = 0; T val = 0;
        for(int i = __lg(n); i >= 0; i--){
            if ((ans | (1 << i)) <= n && val + tr[ans | (1 << i)] <= sum){
                ans |= 1 << i;
                val += tr[ans];
            }
        }
        return ans;
    }
 
};
using BIT = Fenwick<int>;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<int>a(n+1);
    BIT bit(n);
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        bit.modify(i,x);
    }
    for(int i=1;i<=m;i++)
    {
        int op,x,y;
        cin>>op>>x>>y;
        if(op==1)
        {
            bit.modify(x,y);
        }
        else
        {
            cout<<bit.query(x,y)<<'\n';
        }
    }    

    return 0;    
}

区修+点查

树状数组初始值都为0，这是一个差分数组，如果对[l,r]加上某一个数，就modify(l,k)，modify(r+1,-k)，然后如果要点查的话就直接用a[x]+bit.query(x)就行了

#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
template<typename T>
struct Fenwick{
    int n;
    vector<T> tr;
 
    Fenwick(int n) : n(n), tr(n + 1, 0){}
 
    int lowbit(int x){
        return x & -x;
    }
 
    void modify(int x, T c){
        for(int i = x; i <= n; i += lowbit(i)) tr[i] += c;
    }
 
    void modify(int l, int r, T c){
        modify(l, c);
        if (r + 1 <= n) modify(r + 1, -c);
    }
 
    T query(int x){
        T res = T();
        for(int i = x; i; i -= lowbit(i)) res += tr[i];
        return res;
    }
 
    T query(int l, int r){
        return query(r) - query(l - 1);
    }
 
    int find_first(T sum){
        int ans = 0; T val = 0;
        for(int i = __lg(n); i >= 0; i--){
            if ((ans | (1 << i)) <= n && val + tr[ans | (1 << i)] < sum){
                ans |= 1 << i;
                val += tr[ans];
            }
        }
        return ans + 1;
    }
 
    int find_last(T sum){
        int ans = 0; T val = 0;
        for(int i = __lg(n); i >= 0; i--){
            if ((ans | (1 << i)) <= n && val + tr[ans | (1 << i)] <= sum){
                ans |= 1 << i;
                val += tr[ans];
            }
        }
        return ans;
    }
 
};
using BIT = Fenwick<int>;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    BIT bit(n+1);
    for(int i=1;i<=m;i++)
    {
        int op,x;
        cin>>op>>x;
        if(op==1)
        {
            int y,k;
            cin>>y>>k;
            bit.modify(x,k);
            bit.modify(y+1,-k);
        }
        else 
        {
            cout<<a[x]+bit.query(x)<<'\n';
        }
    }

    return 0;    
}

区修+区查

这个是最难的。

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

P3372 【模板】线段树 1

这一道题的区修就是区间加，区查就是区间和。

#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
template<typename T>
struct Fenwick{
    int n;
    vector<T> tr;
 
    Fenwick(int n) : n(n), tr(n + 1, 0){}
 
    int lowbit(int x){// 找到x最低有效位
        return x & -x;
    }
 
    void modify(int x, T c){// 点修
        for(int i = x; i <= n; i += lowbit(i)) tr[i] += c;
    }
 
    void modify(int l, int r, T c){// 区修
        modify(l, c);
        if (r + 1 <= n) modify(r + 1, -c);
    }
 
    T query(int x){// 前缀和
        T res = T();
        for(int i = x; i; i -= lowbit(i)) res += tr[i];
        return res;
    }
 
    T query(int l, int r){// 区间查询
        return query(r) - query(l - 1);
    }
 
    int find_first(T sum){// 查找第一个满足条件的下标（前缀和
        int ans = 0; T val = 0;
        for(int i = __lg(n); i >= 0; i--){
            if ((ans | (1 << i)) <= n && val + tr[ans | (1 << i)] < sum){
                ans |= 1 << i;
                val += tr[ans];
            }
        }
        return ans + 1;
    }
 
    int find_last(T sum){// 查找最后一个满足条件的下标（前缀和）
        int ans = 0; T val = 0;
        for(int i = __lg(n); i >= 0; i--){
            if ((ans | (1 << i)) <= n && val + tr[ans | (1 << i)] <= sum){
                ans |= 1 << i;
                val += tr[ans];
            }
        }
        return ans;
    }
 
};
using BIT = Fenwick<int>;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    BIT d1(n),d2(n);
    vector<int>a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];    
    for(int i=1;i<=n;i++)
    {
        d1.modify(i,a[i]);
        d1.modify(i+1,-a[i]);
        d2.modify(i,i*a[i]);
        d2.modify(i+1,-(i+1)*a[i]);
    }
    for(int i=1;i<=m;i++)
    {
        int op,x,y;
        cin>>op>>x>>y;
        if(op==1)
        {
            int k;
            cin>>k;
            d1.modify(x,k);
            d1.modify(y+1,-k);
            d2.modify(x,k*x);
            d2.modify(y+1,-k*(y+1));
        }
        else
        {
            cout<<(y+1ll)*d1.query(y)-1ll*x*d1.query(x-1)-(d2.query(y)-d2.query(x-1))<<'\n';
        }
    }
    return 0;    
}

in>>op>>x>>y;
if(op==1)
{
int k;
cin>>k;
d1.modify(x,k);
d1.modify(y+1,-k);
d2.modify(x,kx);
d2.modify(y+1,-k(y+1));
}
else
{
cout<<(y+1ll)d1.query(y)-1llx*d1.query(x-1)-(d2.query(y)-d2.query(x-1))<<‘\n’;
}
}
return 0;
}

标签：return,树状,--,modify,cin,int,数组,ans,query
From： https://blog.csdn.net/2301_79872524/article/details/143568141

相关文章

  • Docker 镜像缩小
    背景手动构建的Docker镜像如果体积过大，可以利用slim工具来优化和减小其体积。slim不仅能够有效地缩减镜像大小，还有以下额外好处：减少攻击面：通过精简镜像，移除了不必要的文件和依赖，从而减少了潜在的安全漏洞和攻击面。降低安全风险：较小的镜像意味着更少的软件组件，这有助于......
  • 深入探索ReentrantLock(三)：限时锁申请的艺术
     专栏导航JVM工作原理与实战RabbitMQ入门指南从零开始了解大数据目录前言一、ReentrantLock限时锁申请1.限时锁申请的必要性2.tryLock(longtime,TimeUnitunit)方法讲解3.限时锁的优势与注意事项4.tryLock(longtime,TimeUnitunit)案例总结前言Java并发......
  • 如何通过Python SDK更新Collection中已存在的Doc
    本文介绍如何通过PythonSDK更新Collection中已存在的Doc。说明若更新Doc时指定id不存在，则本次更新Doc操作无效如只更新部分属性fields，其他未更新属性fields默认被置为NonePythonSDK1.0.11版本后，更新Doc时vector变为非必填项前提条件已创建Cluster：创建Cluster。......
  • C语言之输出函数printf以及puts
    printf和puts都是c语言的库函数，都可以输出的函数但他们也存在着一定的区别printf函数：1.功能强大：printf是一个格式化输出的函数，它可以输出各种类型的数据，并且能够按照指定的格式进行输出，例如会以10进制整数输出10。可以同时输入多组数据，灵活的控制输出的格式，如控制整数的......
  • 【系统集成项目管理工程师教程】第8章 信息安全工程
    信息安全工程围绕信息安全管理、信息安全系统及工程体系架构展开，涵盖安全保障要求、管理内容、管理体系、等级保护、安全机制、安全服务等多方面，致力于保障信息系统安全，适应时代发展需求，对组织信息化建设与运营意义重大，能有效应对各类安全挑战，确保信息资产保密性、完整性和......
  • 将doc文件转换为docx文件
    将.doc文件转换为.docx文件通常不会导致兼容性变差，反而可能提升兼容性。以下是一些关键点：文件格式更新：.docx是Microsoft在2007年引入的新版文件格式，基于开放XML标准，具有更好的跨平台兼容性和开放性。与旧的.doc格式相比，.docx文件通常更小，支持更多的格式和功......
  • 为什么要对参考文献著录进行要求？
    对参考文献著录进行规范要求有几个重要的原因：确保学术严谨性和规范性：参考文献的规范格式可以确保文献来源清晰、信息准确、便于他人查阅。这体现了学术研究的严谨态度，并帮助防止错误或误解。便于读者查阅和核实：规范的文献格式让读者可以轻松找到引用的资料来源，便于追溯......
  • 分节符的作用是什么？
    分节符在Word文档中有非常重要的作用，它用于将文档划分为不同的“节”。每个节可以独立设置页面格式、页眉页脚等，从而实现灵活的排版效果。以下是分节符的主要作用：独立页面设置分节符允许在同一文档中为不同部分设置独立的页面格式。例如，不同节可以设置不同的页面方向（如部......
  • 多维视角下的知识管理：Spring Boot应用
    2开发技术2.1VUE框架Vue.js（读音/vjuː/,类似于view）是一套构建用户界面的渐进式框架。Vue只关注视图层，采用自底向上增量开发的设计。Vue的目标是通过尽可能简单的API实现响应的数据绑定和组合的视图组件。2.2Mysql数据库关于程序的数据结构设计，数据的字段......
  • Spring Boot框架的知识分类技术解析
    2开发技术2.1VUE框架Vue.js（读音/vjuː/,类似于view）是一套构建用户界面的渐进式框架。Vue只关注视图层，采用自底向上增量开发的设计。Vue的目标是通过尽可能简单的API实现响应的数据绑定和组合的视图组件。2.2Mysql数据库关于程序的数据结构设计，数据的字段......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99