树状数组原理和代码

树状数组

求下标的对应

求i管着的下标的范围

方法：拆掉最右侧的1然后+1  到你自己

query sum

1-i的和

拆掉最右侧的1 再把下一个数值吸收到sum 重复这个过程直到全变0为止

add

方法：加上最右侧的1 到上限为止

lowbit方法

单点增加范围查询模板

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include<vector>
#include<climits>
#include<cmath>
using namespace std;
typedef long long LL;
const int N=5e5+10;
int tree[N];
int n,m;

int lowbit(int i){
	return i&-i;
}

void add(int i,int v){
	while(i<=n){
		tree[i]+=v;
		i+=lowbit(i);
	}
}

int sum(int i){
	int ans=0;
	while(i>0){
		ans+=tree[i];
		i-=lowbit(i);
	}
	return ans;
}

int range(int l,int r){
	return sum(r)-sum(l-1);
}

int main() {
    ios::sync_with_stdio(false); // 可选的，用于加快I/O
    cin.tie(0);
    while (cin >> n >> m) {
        for (int i = 1, v; i <= n; i++) {
            cin >> v;
            add(i, v);
        }
        for (int i = 1, a, b, c; i <= m; i++) {
            cin >> a >> b >> c;
            if (a == 1) {
                add(b, c);
            } else {
                cout << range(b, c) << '\n';
            }
        }
    }
    return 0;
}

范围增加单点查询的模板

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include<vector>
#include<climits>
#include<cmath>
using namespace std;
typedef long long LL;
const int N=5e5+10;
int tree[N];
int n,m;

int lowbit(int i){
	return i&-i;
}

void add(int i,int v){
	while(i<=n){
		tree[i]+=v;
		i+=lowbit(i);
	}
}

int sum(int i){
	int ans=0;
	while(i>0){
		ans+=tree[i];
		i-=lowbit(i);
	}
	return ans;
}

int range(int l,int r){
	return sum(r)-sum(l-1);
}

int main() {
    
    while (cin >> n >> m) {
        for (int i = 1, v; i <= n; i++) {
            cin >> v;
            add(i, v);
            add(i + 1, -v);
        }
        for (int i = 1; i <= m; i++) {
            int op;
            cin >> op;
            if (op == 1) {
                int l, r, v;
                cin >> l >> r >> v;
                add(l, v);
                add(r + 1, -v);
            } else {
                int index;
                cin >> index;
                cout << sum(index) << '\n';
            }
        }
    }
    return 0;
}

树状数组实现范围增加范围查询

#include <iostream>
using namespace std;

const int MAXN = 100001;
long long info1[MAXN]; // 维护原始数组的差分信息：Di
long long info2[MAXN]; // 维护原始数组的差分加工信息：(i-1) * Di
int n, m;

int lowbit(int i) {
    return i & -i;
}

void add(long long tree[], int i, long long v) {
    while (i <= n) {
        tree[i] += v;
        i += lowbit(i);
    }
}

long long sum(long long tree[], int i) {
    long long ans = 0;
    while (i > 0) {
        ans += tree[i];
        i -= lowbit(i);
    }
    return ans;
}

void rangeAdd(int l, int r, long long v) {
    add(info1, l, v);
    add(info1, r + 1, -v);
    add(info2, l, (l - 1) * v);
    add(info2, r + 1, -(r * v));
}

long long rangeQuery(int l, int r) {
    return sum(info1, r) * r - sum(info2, r) - sum(info1, l - 1) * (l - 1) + sum(info2, l - 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    long long cur;
    for (int i = 1; i <= n; ++i) {
        cin >> cur;
        rangeAdd(i, i, cur);
    }
    int op, l, r;
    long long v;
    for (int i = 1; i <= m; ++i) {
        cin >> op;
        if (op == 1) {
            cin >> l >> r >> v;
            rangeAdd(l, r, v);
        } else {
            cin >> l >> r;
            cout << rangeQuery(l, r) << '\n';
        }
    }

    return 0;
}

相关题目

逆序对

归并分治法

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 500001;
int arr[MAXN];
int help[MAXN];
int n;
long long merge(int l, int m, int r);

long long f(int l, int r) {
    if (l == r) {
        return 0;
    }
    int m = (l + r) / 2;
    return f(l, m) + f(m + 1, r) + merge(l, m, r);
}

long long merge(int l, int m, int r) {
    long long ans = 0;
    // 统计逆序对数量
    for (int i = m, j = r; i >= l; i--) {
        while (j >= m + 1 && arr[i] <= arr[j]) {
            j--;
        }
        ans += j - m;
    }
    // 归并排序，让arr[l...r]变成有序
    int i = l, a = l, b = m + 1;
    while (a <= m && b <= r) {
        help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
    }
    while (a <= m) {
        help[i++] = arr[a++];
    }
    while (b <= r) {
        help[i++] = arr[b++];
    }
    for (i = l; i <= r; i++) {
        arr[i] = help[i];
    }
    return ans;
}

int main() {
   

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }

    cout << f(1, n) << '\n';
    return 0;
}

树状数组解法

去重+离散化

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 500001;
int arr[MAXN];
int sortArr[MAXN]; // 用于排序和去重的数组
int tree[MAXN]; // 树状数组
int n, m; // n为数组长度，m为离散化后的值域大小

int lowbit(int x) {
    return x & (-x);
}

void add(int idx, int val) {
    while (idx <= m) {
        tree[idx] += val;
        idx += lowbit(idx);
    }
}

long long sum(int idx) {
    long long res = 0;
    while (idx > 0) {
        res += tree[idx];
        idx -= lowbit(idx);
    }
    return res;
}

// 离散化函数，将数组arr中的值映射到1~m
void discretization() {
    sort(sortArr + 1, sortArr + n + 1);
    m = unique(sortArr + 1, sortArr + n + 1) - (sortArr + 1); // unique返回去重后的尾后迭代器
    for (int i = 1; i <= n; ++i) {
        arr[i] = lower_bound(sortArr + 1, sortArr + m + 1, arr[i]) - sortArr;
    }
}

long long compute() {
    long long ans = 0;
    for (int i = n; i >= 1; --i) {
        ans += sum(arr[i] - 1);
        add(arr[i], 1);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false); // 关闭同步
    cin.tie(0); // 解除cin和cout的绑定
    cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
        sortArr[i] = arr[i];
    }

    discretization(); // 离散化处理
    cout << compute() << endl; // 计算逆序对数量并输出

    return 0;
}

上升三元组

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int MAXN = 30001;
int arr[MAXN], sortArr[MAXN];
long long tree1[MAXN], tree2[MAXN];
int n, m;

int lowbit(int i) {
    return i & -i;
}

void add(long long tree[], int i, long long c) {
    while (i <= m) {
        tree[i] += c;
        i += lowbit(i);
    }
}

long long sum(long long tree[], int i) {
    long long ans = 0;
    while (i > 0) {
        ans += tree[i];
        i -= lowbit(i);
    }
    return ans;
}

long long compute() {
    copy(arr + 1, arr + n + 1, sortArr + 1);
    sort(sortArr + 1, sortArr + n + 1);
    m = unique(sortArr + 1, sortArr + n + 1) - (sortArr + 1);
    for (int i = 1; i <= n; i++) {
        // Using lower_bound to replace the manual rank function
        arr[i] = lower_bound(sortArr + 1, sortArr + m + 1, arr[i]) - sortArr;
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += sum(tree2, arr[i] - 1);
        add(tree1, arr[i], 1);
        add(tree2, arr[i], sum(tree1, arr[i] - 1));
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    cout << compute() << endl;
    return 0;
}

最长递增子序列个数

673. 最长递增子序列的个数

#include <vector>
#include <algorithm>
#include <numeric> // 用于iota函数
using namespace std;

class Solution {
public:
    static const int MAXN = 2001; // 设置最大数值范围
    vector<int> treeMaxLen = vector<int>(MAXN, 0); // 以数值i结尾的最长递增子序列的长度
    vector<int> treeMaxLenCnt = vector<int>(MAXN, 0); // 以数值i结尾的最长递增子序列的个数
    int m; // 数组去重排序后的长度

    int lowbit(int i) {
        return i & (-i);
    }

    void query(int i, int& maxLen, int& maxLenCnt) {
        maxLen = maxLenCnt = 0;
        while (i > 0) {
            if (treeMaxLen[i] == maxLen) {
                maxLenCnt += treeMaxLenCnt[i];
            } else if (treeMaxLen[i] > maxLen) {
                maxLen = treeMaxLen[i];
                maxLenCnt = treeMaxLenCnt[i];
            }
            i -= lowbit(i);
        }
    }

    void add(int i, int len, int cnt) {
        while (i <= m) {
            if (treeMaxLen[i] == len) {
                treeMaxLenCnt[i] += cnt;
            } else if (treeMaxLen[i] < len) {
                treeMaxLen[i] = len;
                treeMaxLenCnt[i] = cnt;
            }
            i += lowbit(i);
        }
    }

    int findNumberOfLIS(vector<int>& nums) {
    if (nums.empty()) return 0;
    vector<int> sortedNums(nums.begin(), nums.end());
    sort(sortedNums.begin(), sortedNums.end());
    auto it = unique(sortedNums.begin(), sortedNums.end()); // 去重，it指向去重后新的末尾
    m = distance(sortedNums.begin(), it); // 使用迭代器之间的距离作为去重后数组的长度

    // 根据去重后的长度调整树状数组的大小
    treeMaxLen.assign(m + 1, 0);
    treeMaxLenCnt.assign(m + 1, 0);

    for (int num : nums) {
        // 注意这里的lower_bound的范围，应当是begin()到it
        int i = lower_bound(sortedNums.begin(), it, num) - sortedNums.begin() + 1; // 获取排名（1-based）
        int maxLen, maxLenCnt;
        query(i - 1, maxLen, maxLenCnt);
        add(i, maxLen + 1, maxLenCnt == 0 ? 1 : maxLenCnt);
    }
    int totalMaxLen = 0, totalCount = 0;
    query(m, totalMaxLen, totalCount);
    return totalCount;
}

};

P1972 [SDOI2009] HH的项链

每种颜色只留最右边的

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>

using namespace std;

const int MAXN = 1000010;
int arr[MAXN], ans[MAXN], map[MAXN], tree[MAXN], n, m;

struct Query {
    int l, r, idx;
    Query(int l = 0, int r = 0, int idx = 0) : l(l), r(r), idx(idx) {}
};

vector<Query> queries(MAXN);

int lowbit(int i) {
    return i & -i;
}

void add(int i, int v) {
    while (i <= n) {
        tree[i] += v;
        i += lowbit(i);
    }
}

int sum(int i) {
    int ans = 0;
    while (i > 0) {
        ans += tree[i];
        i -= lowbit(i);
    }
    return ans;
}

int range(int l, int r) {
    return sum(r) - sum(l - 1);
}

void compute() {
    sort(queries.begin() + 1, queries.begin() + m + 1, [](const Query& a, const Query& b) {
        return a.r < b.r;
    });
    for (int s = 1, q = 1; q <= m; q++) {
        int r = queries[q].r;
        for (; s <= r; s++) {
            if (map[arr[s]] != 0) {
                add(map[arr[s]], -1);
            }
            add(s, 1);
            map[arr[s]] = s;
        }
        ans[queries[q].idx] = range(queries[q].l, r);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &arr[i]);
    }
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        int l, r;
        scanf("%d %d", &l, &r);
        queries[i] = Query(l, r, i);
    }
    compute();
    for (int i = 1; i <= m; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/485306.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Redis持久化【RDB，bgsave的写时复制机制】【AOF，aof重写机制】【Redis混合持久化，以及对应改变aof重写规则】【Redis数据备份策略】

Redis持久化【RDB，bgsave的写时复制机制】【AOF，aof重写机制】【Redis混合持久化，以及对应改变aof重写规则】【Redis数据备份策略】

Redis持久化 RDB快照&#xff08;snapshot&#xff09;bgsave的写时复制(COW)机制 AOF&#xff08;append-only file&#xff09;AOF重写 Redis 4.0 混合持久化开启持久化后&#xff0c;AOF重写规则发生了变化 Redis数据备份策略&#xff1a; 转自 图灵课堂 RDB快照&#xff0…
阅读更多...
第390场 LeetCode 周赛题解

第390场 LeetCode 周赛题解

A 每个字符最多出现两次的最长子字符串 滑动窗口&#xff1a;枚举窗口的左边界&#xff0c;尽可能右移窗口的右边界。 (当然也可以暴力枚举) class Solution { public:int maximumLengthSubstring(string s) {vector<int> cnt(26);int res 0;for (int l 0, r -1, n s…
阅读更多...
python第三方库的安装，卸载和更新，以及在cmd下pip install安装的包在pycharm不可用问题的解决

python第三方库的安装，卸载和更新，以及在cmd下pip install安装的包在pycharm不可用问题的解决

目录 第三方库pip安装&#xff0c;卸载更新 1.安装&#xff1a; 2.卸载 3.更新 一、第三方库pip安装&#xff0c;卸载更新 1.安装 pip install 模块名 加镜像下载&#xff1a;pip install -i 镜像网址模块名 常用的是加清华镜像&#xff0c;如 pip install -i https://pyp…
阅读更多...
jmeter链路压测

jmeter链路压测

比如登录后返回token&#xff0c;业务打印上传的操作需要用到token 线程组中添加登录请求&#xff0c;并执行 1、添加登录并执行&#xff0c;查看结果 2、结果树中下拉选择正则表达式&#xff0c;将token参数和值复制粘贴到下方&#xff0c;将token值改为(.*?)&#xff0…
阅读更多...
Pinctrl子系统_05_Pincontroller构造过程情景分析

Pinctrl子系统_05_Pincontroller构造过程情景分析

上一节我们了解了Pinctrl子系统主要的数据结构&#xff0c;要想更好的掌握Pinctrl子系统&#xff0c;还需要知道他的构造过程。 本节我们就来分析一下Pinctrl子系统的构造过程。 以内核面向对象的思想&#xff0c;设备树可以分为两部分&#xff0c;左边是Pinctrl子系统节点&a…
阅读更多...
毕业论文降重（gpt+完美降重指令），sci论文降重gpt指令——超级好用，重复率低于4%

毕业论文降重（gpt+完美降重指令），sci论文降重gpt指令——超级好用，重复率低于4%

1. 降重方法&#xff1a;gpt降重指令 2. gpt网站 https://yiyan.baidu.com/ https://chat.openai.com/ 3. 降重指令——非常好用&#xff01;&#xff01;sci论文&#xff0c;本硕大论文都可使用&#xff01; 请帮我把下面句子重新组织&#xff0c;通过调整句子逻辑&#xff0…
阅读更多...
牛客NC218 检测循环依赖【中等 图 Java，Go，PHP】

牛客NC218 检测循环依赖【中等 图 Java，Go，PHP】

题目 题目链接&#xff1a; https://www.nowcoder.com/practice/8dc02ad98553432a90affc3a0484910b 思路 图的基本知识要理解&#xff0c;一般用Map来表示 图解决拓扑排序&#xff0c;依赖之类的问题 感觉课程数在这道题里面可以不用&#xff0c;因为没有规定所有课程都得有先…
阅读更多...
解决方案Please use Oracle(R) Java(TM) 11, OpenJDK(TM) 11 to run Neo4j.

解决方案Please use Oracle(R) Java(TM) 11, OpenJDK(TM) 11 to run Neo4j.

文章目录 一、现象二、解决方案 一、现象 当安装好JDK跟neo4j&#xff0c;用neo4j.bat console来启动neo4却报错&#xff1a; 部分报错信息&#xff1a; Starting Neo4j. WARNING! You are using an unsupported Java runtime. Please use Oracle Java™ 11, OpenJDK™ 11 t…
阅读更多...
Jenkins中使用Generic Webhook Trigger插件实现持续集成

Jenkins中使用Generic Webhook Trigger插件实现持续集成

项目环境 宝塔Linux面板DockerJenkinsgitee 目的 实现每次push推送dev分支到gitee上&#xff0c;Jenkins自动构建项目&#xff1b;push其它分支时&#xff0c;不运行。 实现方法 1.在Jenkins上安装Generic Webhook Trigger插件 在“系统设置–插件管理–可选插件”界面搜…
阅读更多...
jmeter中参数加密

jmeter中参数加密

加密接口常用的方式有&#xff1a; MD5&#xff0c;SHA&#xff0c;HmacSHA RSA AES&#xff0c;DES&#xff0c;Base64 压测中有些参数需要进行加密&#xff0c;加密方式已接口文档为主。 MD5加密 比如MD5加密的接口文档&#xff1a; 请求URL&#xff1a;http://101.34.221…
阅读更多...
STM32 | Systick定时器(第四天源码解析)

STM32 | Systick定时器(第四天源码解析)

STM32 | Systick定时器(第四天)STM32 | STM32F407ZE中断、按键、灯（续第三天）1、参考delay_us代码，完成delay_ms的程序 定时器频率换算单位：1GHZ=1000MHZ=1000 000KHZ = 1000 000 000HZ 定时器定时时间：计数个数/f(频率) 或者 (1/f(频率))*计数的个数 500/1MHZ = 500/1…
阅读更多...
Spring相关框架八股

Spring相关框架八股

单例bean是线程安全的吗&#xff1f; AOP 事务失效 Bean生命周期 Bean循环依赖解决 MVC执行流程 自动装配原理 Spring常见注解 SpringMVC注解 SpringBoot注解 MyBatis执行流程 MyBatis延迟加载 MyBatis缓存 SpringCloud五大组件 注册中心Nacos、Eureka 负载均衡Ribbon 服务雪崩…
阅读更多...
Godot.NET C# 工程化开发(1):通用Nuget 导入+ 模板文件导出，包含随机数生成，日志管理，数据库连接等功能

Godot.NET C# 工程化开发(1):通用Nuget 导入+ 模板文件导出，包含随机数生成，日志管理，数据库连接等功能

文章目录 前言Github项目地址&#xff0c;包含模板文件后期思考补充项目设置编写失误环境visual studio 配置详细的配置看我这篇文章 Nuget 推荐NewtonSoft 成功Bogus 成功Github文档地址随机生成构造器生成构造器接口(推荐) 文件夹设置Nlog 成功&#xff01;Nlog.configNlogHe…
阅读更多...
2025汤家凤考研数学视频，基础网课百度网盘课程+PDF讲义资料

2025汤家凤考研数学视频，基础网课百度网盘课程+PDF讲义资料

2025汤家凤大神及数学全程 docs.qq.com/doc/DTmtOa0Fzc0V3WElI 复制粘贴到浏览器&#xff0c;可以见所有的Ke 第一轮 夯实基础 1.阅读大纲考查要求&#xff0c;明确每章的学习目标&#xff1b; 2.按节学习数学理论基础知识&#xff0c;吃透书中例题&#xff1b; 3.学习每章…
阅读更多...
红外遥控器的使用和详细解释

红外遥控器的使用和详细解释

infrared.c #include "infrared.h"/* 红外 --- PA8*/void Infrared_Init(void) {GPIO_InitTypeDef GPIO_InitStruct; EXTI_InitTypeDef EXTI_InitStruct;NVIC_InitTypeDef NVIC_InitStruct;//使能SYSCFG时钟RCC_APB2PeriphClockCmd(RCC_APB2Periph_SYSCFG, E…
阅读更多...
【数据结构】五分钟自测主干知识（十）

【数据结构】五分钟自测主干知识（十）

上一节&#xff0c;我们讲述了二叉树的概念&#xff0c;二叉树又有什么基本操作呢&#xff1f;今天我们来讲述二叉树的应用~ 话不多说&#xff0c;书继上回 5.3二叉树的遍历及应用 二叉树由三个基本部分组成&#xff1a;根结点&#xff08;D&#xff09;&#xff0c;左子树&a…
阅读更多...
ForkJoinPool在生产环境中使用遇到的一个问题

ForkJoinPool在生产环境中使用遇到的一个问题

1、背景 在我们的项目中有这么一个场景&#xff0c;需要消费kafka中的消息&#xff0c;并生成对应的工单数据。早些时候程序运行的好好的&#xff0c;但是有一天&#xff0c;我们升级了容器的配置&#xff0c;结果导致部分消息无法消费。而消费者的代码是使用CompletableFutur…
阅读更多...
综合知识篇21-项目管理考点（2024年软考高级系统架构设计师冲刺知识点总结系列文章）

综合知识篇21-项目管理考点（2024年软考高级系统架构设计师冲刺知识点总结系列文章）

专栏系列文章： 2024高级系统架构设计师备考资料（高频考点&真题&经验）https://blog.csdn.net/seeker1994/category_12593400.html案例分析篇00-【历年案例分析真题考点汇总】与【专栏文章案例分析高频考点目录】（2024年软考高级系统架构设计师冲刺知识点总结-案例…
阅读更多...
数据结构:插入排序,希尔排序(缩小增量排序)

数据结构:插入排序,希尔排序(缩小增量排序)

1.直接插入排序 当插入第 i 个元素时,前面的数据已经排好序了,将后续的数据按大小插入到前面已经排好序的数组中,就是插入排序 特点 1.元素集合越接近有序,时间效率越高 2.时间复杂度O(N^2) 3.空间复杂度O(1) //插入排序 void InsertSort(int* a, int length) {for (int …
阅读更多...
2021年XX省赛职业院校技能大赛”高职组 计算机网络应用赛项 网络构建模块竞赛真题

2021年XX省赛职业院校技能大赛”高职组 计算机网络应用赛项 网络构建模块竞赛真题

“2021年XX省赛职业院校技能大赛”高职组 计算机网络应用赛项 网络构建模块竞赛真题 目录 一&#xff0e;考试说明 1 二&#xff0e;模块B网络构建 2 &#xff08;一&#xff09;任务描述 2 &#xff08;二&#xff09;任务清单 9 一&#xff0e;考试说明 本模块比赛时间为…
阅读更多...
最新文章

Copyright @ 2022~2023